Groth16 A successor to Pinocchio Proofs are 3 elements, rather than 8 Verification is 3 pairings, rather than 12 Trusted Setup α , β , τ , γ , δ ← random scalars [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) δ , τ n − 3 t ( τ ) δ , . . . , τ t ( τ ) δ , t ( τ ) δ ] ← SRS for h ( τ ) t ( τ ) \begin{aligned} \alpha,\beta,\tau,\gamma,\delta &\leftarrow& \text{random scalars}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow& \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow& \text{SRS for } \mathbb{G}_2\\ \\ [\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow&\text{SRS for } h(\tau)t(\tau)\\ \\ \end{aligned} α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) , δ τ n − 3 t ( τ ) , ... , δ τ t ( τ ) , δ t ( τ ) ] ← ← ← ← random scalars SRS for G 1 SRS for G 2 SRS for h ( τ ) t ( τ ) Used with public portion of witness [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ G 1 [ Ψ 2 ] 1 = α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) γ G 1 ⋮ [ Ψ l ] 1 = α v l ( τ ) + β u l ( τ ) + w l ( τ ) γ G 1 Used with private portion of witness [ Ψ l + 1 ] 1 = α v l + 1 ( τ ) + β u l + 1 ( 1 τ ) + w l + 1 ( τ ) δ G 1 [ Ψ l + 2 ] 1 = α v l + 2 ( τ ) + β u l + 2 ( τ ) + w l + 2 ( τ ) δ G 1 ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ G 1 \begin{aligned} &&\text{Used with public portion of witness}\\ [\Psi_1]_1&=&\frac{\alpha v_1(\tau)+\beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\ [\Psi_2]_1&=&\frac{\alpha v_2(\tau)+\beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\ \vdots&&\\ [\Psi_l]_1&=&\frac{\alpha v_l(\tau)+\beta u_l(\tau) + w_l(\tau)}{\gamma}G_1\\ \\ &&\text{Used with private portion of witness}\\ [\Psi_{l+1}]_1&=&\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(1\tau) + w_{l+1}(\tau)}{\delta}G_1\\ [\Psi_{l+2}]_1&=&\frac{\alpha v_{l+2}(\tau)+\beta u_{l+2}(\tau) + w_{l+2}(\tau)}{\delta}G_1\\ \vdots&&\\ [\Psi_m]_1&=&\frac{\alpha v_m(\tau)+\beta u_m(\tau) + w_m(\tau)}{\delta}G_1\\ \end{aligned} [ Ψ 1 ] 1 [ Ψ 2 ] 1 ⋮ [ Ψ l ] 1 [ Ψ l + 1 ] 1 [ Ψ l + 2 ] 1 ⋮ [ Ψ m ] 1 = = = = = = Used with public portion of witness γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) G 1 γ α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) G 1 γ α v l ( τ ) + β u l ( τ ) + w l ( τ ) G 1 Used with private portion of witness δ α v l + 1 ( τ ) + β u l + 1 ( 1 τ ) + w l + 1 ( τ ) G 1 δ α v l + 2 ( τ ) + β u l + 2 ( τ ) + w l + 2 ( τ ) G 1 δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 1 Publishes ( [ α ] 1 , [ β ] 1 [ β ] 2 , [ γ ] 2 , [ δ ] 1 [ δ ] 2 , S R S G 1 , S R S G 2 , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , . . . , [ Ψ m ] 1 ) ([\alpha]_1,\ [\beta]_1[\beta]_2,\ [\gamma]_2,\ [\delta]_1[\delta]_2,\ SRS_{G_1},\ SRS_{G_2},\ [\Psi_1]_1,\ [\Psi_2]_1,\ ..., [\Psi_m]_1) ([ α ] 1 , [ β ] 1 [ β ] 2 , [ γ ] 2 , [ δ ] 1 [ δ ] 2 , SR S G 1 , SR S G 2 , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , ... , [ Ψ m ] 1 )
Base Trusted Setup τ ← random scalar, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , . . . , τ t ( τ ) , t ( τ ) ] ← SRS for h ( τ ) t ( τ ) Publishes [ S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) ] Prover [ A ] 1 = ∑ i = 1 m a i u ( τ ) [ B ] 2 = ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = 1 m a i w ( τ ) + h ( τ ) t ( τ ) Verifier [ A ] 1 ∙ [ B ] 2 = ? [ C ] 1 ∙ [ G ] 2 \begin{aligned} \text{Trusted Setup}\\ \tau &\leftarrow \text{random scalar, toxic waste}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\ [\tau^{n-2}t(\tau),\ \tau^{n-3}t(\tau),\ ...,\ \tau t(\tau),\ t(\tau)] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\ \\ \text{Publishes}\\ [SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}]\\ \\ \text{Prover}\\ [A]_1&=\sum^m_{i=1}a_iu(\tau)\\ [B]_2&=\sum^m_{i=1}a_iv(\tau)\\ [C]_1&=\sum^m_{i=1}a_iw(\tau)+h(\tau)t(\tau)\\ \\ \text{Verifier}\\ [A]_1\bullet[B]_2&\stackrel{?}{=}[C]_1\bullet[G]_2\\ \end{aligned} Trusted Setup τ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , ... , τ t ( τ ) , t ( τ )] Publishes [ SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ A ] 1 ∙ [ B ] 2 ← random scalar, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) G 2 , SR S h ( τ ) t ( τ ) ] = i = 1 ∑ m a i u ( τ ) = i = 1 ∑ m a i v ( τ ) = i = 1 ∑ m a i w ( τ ) + h ( τ ) t ( τ ) = ? [ C ] 1 ∙ [ G ] 2 Soundness Trusted Setup α , β , τ ← random scalars, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , . . . , τ t ( τ ) , t ( τ ) ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) Publishes ( [ α ] 1 , [ β ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) Verifier [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ [ G ] 2 \begin{aligned} \text{Trusted Setup}\\ \alpha,\beta,\tau &\leftarrow \text{random scalars, toxic waste}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\ [\tau^{n-2}t(\tau),\ \tau^{n-3}t(\tau),\ ...,\ \tau t(\tau),\ t(\tau)] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\ \\ [\Psi_1]_1&=\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)\\ &\vdots\\ [\Psi_m]_1&=\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)\\ \\ \text{Publishes}\\ ([\alpha]_1, [\beta]_2, SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\ \\ \text{Prover}\\ [A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau)\\ [B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau)\\ [C]_1&=\sum^m_{i=1}a_i[\Psi]_i+h(\tau)t(\tau)\\ \\ \text{Verifier}\\ [A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet[G]_2\\ \end{aligned} Trusted Setup α , β , τ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , ... , τ t ( τ ) , t ( τ )] [ Ψ 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 2 , SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ A ] 1 ∙ [ B ] 2 ← random scalars, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) = [ α ] 1 + i = 1 ∑ m a i u ( τ ) = [ β ] 2 + i = 1 ∑ m a i v ( τ ) = i = 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ [ G ] 2 Part-public witness Trusted Setup α , β , τ ← random scalars, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , . . . , τ t ( τ ) , t ( τ ) ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) Publishes ( [ α ] 1 , [ β ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = l + 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) Verifier [ X ] 1 = ∑ i = 1 l a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ G ] 2 + [ C ] 1 ∙ [ G ] 2 \begin{aligned} \text{Trusted Setup}\\ \alpha,\beta,\tau &\leftarrow \text{random scalars, toxic waste}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\ [\tau^{n-2}t(\tau),\ \tau^{n-3}t(\tau),\ ...,\ \tau t(\tau),\ t(\tau)] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\ \\ [\Psi_1]_1&=\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)\\ &\vdots\\ [\Psi_m]_1&=\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)\\ \\ \text{Publishes}\\ ([\alpha]_1, [\beta]_2, SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\ \\ \text{Prover}\\ [A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau)\\ [B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau)\\ [C]_1&=\sum^m_{i=l+1}a_i[\Psi]_i+h(\tau)t(\tau)\\ \\ \text{Verifier}\\ [X]_1 &= \sum^l_{i=1}a_i\Psi_i\\ [A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [X]_1 \bullet [G]_2 + [C]_1\bullet[G]_2\\ \end{aligned} Trusted Setup α , β , τ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , ... , τ t ( τ ) , t ( τ )] [ Ψ 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 2 , SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ X ] 1 [ A ] 1 ∙ [ B ] 2 ← random scalars, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) = [ α ] 1 + i = 1 ∑ m a i u ( τ ) = [ β ] 2 + i = 1 ∑ m a i v ( τ ) = i = l + 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) = i = 1 ∑ l a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ G ] 2 + [ C ] 1 ∙ [ G ] 2 Fixing soundness Trusted Setup α , β , τ , γ , δ ← random scalars, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) δ , τ n − 3 t ( τ ) δ , . . . , τ t ( τ ) δ , t ( τ ) δ ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ ⋮ [ Ψ l ] 1 = α v l ( τ ) + β u l ( τ ) + w l ( τ ) γ [ Ψ l + 1 ] 1 = α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) δ ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ Publishes ( [ α ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = l + 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) Verifier [ X ] 1 = ∑ i = 1 l a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 \begin{aligned} \text{Trusted Setup}\\ \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{random scalars, toxic waste}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\ [\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\ \\ [\Psi_1]_1&=\frac{\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)}{\gamma}\\ &\vdots\\ [\Psi_l]_1&=\frac{\alpha v_l(\tau)+\beta u_l(\tau)+w_l(\tau)}{\gamma}\\ [\Psi_l+1]_1&=\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(\tau)+w_{l+1}(\tau)}{\delta}\\ &\vdots\\ [\Psi_m]_1&=\frac{\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)}{\delta}\\ \\ \text{Publishes}\\ ([\alpha]_1, [\beta]_2, [\gamma]_2, [\delta]_2, SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\ \\ \text{Prover}\\ [A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau)\\ [B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau)\\ [C]_1&=\sum^m_{i=l+1}a_i[\Psi]_i+h(\tau)t(\tau)\\ \\ \text{Verifier}\\ [X]_1 &= \sum^l_{i=1}a_i\Psi_i\\ [A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [X]_1 \bullet [\gamma]_2 + [C]_1\bullet[\delta]_2\\ \end{aligned} Trusted Setup α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) , δ τ n − 3 t ( τ ) , ... , δ τ t ( τ ) , δ t ( τ ) ] [ Ψ 1 ] 1 [ Ψ l ] 1 [ Ψ l + 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 2 , SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ X ] 1 [ A ] 1 ∙ [ B ] 2 ← random scalars, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = γ α v l ( τ ) + β u l ( τ ) + w l ( τ ) = δ α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) ⋮ = δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) = [ α ] 1 + i = 1 ∑ m a i u ( τ ) = [ β ] 2 + i = 1 ∑ m a i v ( τ ) = i = l + 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) = i = 1 ∑ l a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 Enforcing Zero-Knowledge Trusted Setup α , β , τ , γ , δ ← random scalars [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) δ , τ n − 3 t ( τ ) δ , . . . , τ t ( τ ) δ , t ( τ ) δ ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ ⋮ [ Ψ l ] 1 = α v l ( τ ) + β u l ( τ ) + w l ( τ ) γ [ Ψ l + 1 ] 1 = α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) δ ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ Publishes ( [ α ] 1 , [ β ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 1 , [ δ ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover r , s ← random scalars, toxic waste [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) + r [ δ ] 1 [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) + s [ δ ] 1 [ C ] 1 = ∑ i = l + 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) + [ A ] 1 s + [ B ] 1 r − r s [ δ ] 1 Verifier [ X ] 1 = ∑ i = 1 l a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 \begin{aligned} \text{Trusted Setup}\\ \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{random scalars}\\ [\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\ [\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\ \\ [\Psi_1]_1&=\frac{\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)}{\gamma}\\ &\vdots\\ [\Psi_l]_1&=\frac{\alpha v_l(\tau)+\beta u_l(\tau)+w_l(\tau)}{\gamma}\\ [\Psi_l+1]_1&=\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(\tau)+w_{l+1}(\tau)}{\delta}\\ &\vdots\\ [\Psi_m]_1&=\frac{\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)}{\delta}\\ \\ \text{Publishes}\\ ([\alpha]_1, [\beta]_1, [\beta]_2, [\gamma]_2, [\delta]_1, [\delta]_2,SRS_{\mathbb{G}_1}&, SRS_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\ \\ \text{Prover}\\ r,s &\leftarrow \text{random scalars, toxic waste}\\ [A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau) + r[\delta]_1\\ [B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau) + s[\delta]_1\\ [C]_1&=\sum^m_{i=l+1}a_i[\Psi]_i+h(\tau)t(\tau) + [A]_1s + [B]_1r - rs[\delta]_1\\ \\ \text{Verifier}\\ [X]_1 &= \sum^l_{i=1}a_i\Psi_i\\ [A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [X]_1 \bullet [\gamma]_2 + [C]_1\bullet[\delta]_2\\ \end{aligned} Trusted Setup α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) , δ τ n − 3 t ( τ ) , ... , δ τ t ( τ ) , δ t ( τ ) ] [ Ψ 1 ] 1 [ Ψ l ] 1 [ Ψ l + 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 1 , [ δ ] 2 , SR S G 1 Prover r , s [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ X ] 1 [ A ] 1 ∙ [ B ] 2 ← random scalars ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = γ α v l ( τ ) + β u l ( τ ) + w l ( τ ) = δ α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) ⋮ = δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) , SR S G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) ← random scalars, toxic waste = [ α ] 1 + i = 1 ∑ m a i u ( τ ) + r [ δ ] 1 = [ β ] 2 + i = 1 ∑ m a i v ( τ ) + s [ δ ] 1 = i = l + 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) + [ A ] 1 s + [ B ] 1 r − rs [ δ ] 1 = i = 1 ∑ l a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 QAP Setup a ← witness vector O ← Output matrix L ← LHS Matrix R ← RHS Matrix O a = L a ⋅ R a ↓ O a → ∑ i = 1 m a i w i ( x ) → w ( x ) L a → ∑ i = 1 m a i u i ( x ) → u ( x ) R a → ∑ i = 1 m a i v i ( x ) → v ( x ) O a = L a ⋅ R a → w ( x ) = u ( x ) ⋅ v ( x ) + b ( x ) \begin{aligned} a &\leftarrow \text{witness vector}\\ O &\leftarrow \text{Output matrix}\\ L &\leftarrow \text{LHS Matrix}\\ R &\leftarrow \text{RHS Matrix}\\ \\ Oa &=La\cdot Ra\\\\ & \big\downarrow\\\\ Oa &\rightarrow \sum_{i=1}^ma_iw_i(x) \rightarrow w(x)\\ La &\rightarrow \sum_{i=1}^ma_iu_i(x) \rightarrow u(x)\\ Ra &\rightarrow \sum_{i=1}^ma_iv_i(x) \rightarrow v(x)\\ Oa = La\cdot Ra &\rightarrow w(x) = u(x)\cdot v(x) + b(x)\\ \end{aligned} a O L R O a O a L a R a O a = L a ⋅ R a ← witness vector ← Output matrix ← LHS Matrix ← RHS Matrix = L a ⋅ R a ↓ ⏐ → i = 1 ∑ m a i w i ( x ) → w ( x ) → i = 1 ∑ m a i u i ( x ) → u ( x ) → i = 1 ∑ m a i v i ( x ) → v ( x ) → w ( x ) = u ( x ) ⋅ v ( x ) + b ( x )